HTTP/2 is a new version of the HTTP protocol currently being specified by the IETF (see HTTP version 2, Internet draft dated Feb. 13, 2014, available at http://tools.ietf.org/html/draft-ietf-httpbis-http2-10).
It is well-known that the HTTP protocol allows a client device and a server device to communicate through the exchange of requests and responses. Conventionally, requests are sent by the client device to the server device, which in return, sends responses.
As defined by the IETF, the HTTP requests and responses are transmitted over a TCP connection established between the client device and the server device.
The earliest versions of HTTP relied on different TCP connections to respectively convey each pair of request/response.
The most recent versions of HTTP allow reusing the same TCP connection to exchange a plurality of pairs of (request, response).
In the particular case of HTTP/2, one and the same TCP connection is used between the client and server devices to exchange all the requests and responses. This makes it possible for HTTP/2 to multiplex requests and responses and even to intermingle parts of them. For instance, the client device may start sending a first request, then sends a second request, and then finishes sending its first request. On the other side, the server device may respond to the requests from the client device in any order, for example by intermingling parts of different responses.
To handle efficiently each pair of request and response, and thus to allow efficient multiplexing, HTTP/2 uses a stream identifier (ID), usually a 31-bit integer value, to identify each of the pairs. A stream can be seen as a bidirectional channel between the client and server devices used to exchange one request and the corresponding response in the established TCP connection.
Each time a new request is sent by the client device, a new stream is created. The request is sent through one or more HTTP/2 frames as defined in the above publication, each of them storing the corresponding stream ID in its frame header. The above multiplexing thus consists in multiplexing such HTTP/2 streams within the same TCP connection.
A stream is usually closed once the response associated with a given request has been received by the client device that originated said request.
Since the stream is provided for a single request and the corresponding response, the words “stream” and “request” or “stream” and “response” are indifferently used in the description below because the processing of a request/response by any of the client and server devices means the same as the processing of the corresponding stream by the same device.
Be HTTP/2 or any other protocol where a plurality of requests and responses can be sent in parallel within one and the same connection, the way, and more particularly the order in which, the server device processes the plurality of requests received through the same connection is an issue for the client device. This is because the latter may desire that some requests be processed in priority compared to other requests.
For example, if the client requests two images, one of which is a photo while the other one is a background image, the client may prefer receiving the photo first, which is of more interest to the user. On the contrary, if the two images are two photos from a photo album for example, the client may prefer receiving both photos in parallel in order to start displaying some results to the user as soon as possible. In fact, displaying the images progressively, i.e. starting by low resolution images then full resolution images, makes the displaying looks more reactive to the user compared to the situation where full resolution images are downloaded at first.
HTTP/2 introduces priorities to the requests for the client device to specify in which order it wishes to receive responses corresponding to different requests, or at least to try to drive the server device to process some requests in priority. To do so, the client device may specify a priority parameter value within a frame used to create a new stream, known as HEADERS frame, or within a frame, known as PRIORITY frame, that can be sent at any time for an existing stream to dynamically modify priorities of pending requests.
For example, in the above publication, a 31-bit priority parameter integer value is provided with 0 representing the highest priority and 2^31-1 representing the lowest priority (or vice versa). The priority parameter integer value expresses the relative priority of a stream (or a request). The server device can use (but this is not mandatory) this information to preferentially order the processing of received requests.
In HTTP/2, the prioritization information sent by the client device is used by the server device to create a dependency tree between the received requests (streams). The “dependency tree” is also referred to as a “priority tree” and the two terms are indifferently used in the description below.
In the dependency tree, a first stream can be made dependent on a second stream, which means that processing the first stream shouldn't occur before the completion of the processing of the second stream. Two streams can be made dependent on the same parent stream. Once the processing of the parent stream is completed, the two dependent streams are processed in parallel. In other words, a dependent stream should be allocated resources by the server only if all of the streams that it depends on (the chain of parent streams up to the root of the tree) are either closed, or it is not possible to make progress on them.
In addition, all dependent streams may be allocated an integer weight between 1 and 256 representing the proportion of resources allocated to them, i.e. streams with the same parent should be allocated resources proportionally to their weight. Thus, if stream B depends on stream A and B is assigned a weight 4, and C depends on stream A and C is assigned a weight 12, and if no progress can be made on A, stream B ideally receives one third of the resources allocated to stream C.
Resources necessary to process a request may be of different types and may include CPU processing time, system memory and network bandwidth for sending the response back to the client device. The resources may also include storage-related resources such as a hard disk, or database-related resources. Among these resources, the bandwidth has usually the strongest impact on the response time, and it can be easily split between several streams, allowing a parallel transmission of several responses.
In the example of FIG. 1a, both streams B and C depend on the same parent stream A. This means that the server should first process stream A, then, once the processing of stream A is completed, the server processes streams B and C in parallel. In addition, the weight assigned to B is 16, while the weight assigned to C is 32, meaning two times more resources should be allocated to C than to B. In particular, this means that C should receive ⅔ of the bandwidth, while B receives only ⅓ of the bandwidth.
A new stream is by default not dependent on any other stream, but is instead a new top level stream, being as such processed in parallel with all the other top level streams. The client can chose to make the new stream dependent on another existing stream, either by adding it as a new dependent stream on the existing stream, or inserting it between the existing stream and its existing dependencies. In the example of FIG. 1b, the stream D is added as a new dependency of stream A, and will be processed in parallel with the existing dependencies B and C. In the example of FIG. 1c, the stream D is added as an exclusive dependency of stream A, the existing dependencies of A, streams B and C, become dependencies of this new stream D. Stream D will be processed after stream A, but before streams B and C.
A stream can be removed for the dependency tree, for example when it is closed, meaning that both the request and the response transmitted over it are finished. In this case, any stream depending on it becomes dependent on its parent. In addition its weight is split between its dependencies, according to their relative weights. For example, in FIG. 1e, stream B is removed (from left tree in the figure). The two dependencies of stream B, streams D and E become dependent on its parent stream, A (right tree in the figure). The weight of stream B, 16, is split between D and E, according to their relative weight. The new weight of D is 16*4/(4+8)=5.3, while the new weight of E is 16*8/(4+8)=10.7.
If the removed stream was a top level stream, then its dependencies become top level streams.
The prioritization of one or several streams can be changed after their creation. The client can change the priority of an existing stream by changing the parent stream it depends on and/or by changing its weight. When changing the parent stream of a given stream, the stream is moved with all its dependencies. In the example of FIG. 1d, the stream B initially depending on stream A (left tree) is reprioritized to depend on stream C (right tree). Stream D remains dependent on stream B through this reprioritization process.
Because of memory constraints, the server device should keep the total number of recorded streams in the dependency tree under a certain limit.
When a stream is removed from the dependency tree, its dependencies are moved/placed to become dependent on the parent of the closed stream. The weights of new dependencies are recalculated by distributing the weight of the dependency of the closed stream proportionally based on the weights of its dependencies.
Streams that are removed from the dependency tree cause some prioritization information to be lost.
For example, taking the priority tree of FIG. 1a, the client may want to add a new stream D, depending on stream B. It sends a message to the server for creating this stream and defining its priority. If the server has finished processing and sending the response on stream B, it may not only have closed stream B, but also discarded any information about stream B from its memory. In this case, upon receiving the stream creation order from the client and the associated priority definition, the server is able to create the new stream D, but it is not able to insert it correctly in the priority tree. Hence, the server will not be able to process the different requests in the order best suited to the client. This can lead at best to inefficiencies, or at worse, to bad user experience.
HTTP/2 specification recommends that the size limit of the dependency tree should be at least equal to the maximum number of streams that the client can open simultaneously, and that a stream should be kept some time after it is closed. But these basic rules are not sufficient to provide good performances and optimal user experience.
The present invention has been devised to address at least one of the foregoing concerns.